package org.bridgen.test.compare;

import java.util.Iterator;
import java.util.LinkedList;

/**
 * 
 * @author Emma Söderberg <emma add cs.lth.se>
 *
 */

public class DistanceFunction {

	protected int maxDistanceValue = Integer.MAX_VALUE/10; // We have to put something big but we can't risk the whole thing..
	protected int minDistanceValue = 0;

	protected CostFunction cf;

	public DistanceFunction(CostFunction cf) {
		this.cf = cf;
	}

	/* Required by Lemma 1 */

	// D(@,@)
	public int distance(Tree.Empty empty, Tree.Empty empty2) { 
		return minDistanceValue; 
	}
	
	// F(@,@)
	public int distance(Forest.Empty empty, Forest.Empty empty2) {
		return minDistanceValue;
	}

	// D(F_1[i],@)
	public int distance(Forest f1, Forest.Empty empty) {
		return distance(f1, 1, f1.degree(), empty);
	}
	
	// Generalised version: D(F_1[i_s0,i_s],@)
	public int distance(Forest f1, int s0, int s, Forest.Empty empty) {
		if (!register(f1,s0,s,empty,0,0)) {
			return maxDistanceValue;
		}
		
		Forest.Interval f1Int = f1.interval(s0, s);
		Forest.Interval emptyInt = empty.fullInterval();
		if (f1.hasValueInCacheFor(f1Int, emptyInt)) {
			unregister(f1,s0,s,empty,0,0);
			return f1.getCachedValue(f1Int, emptyInt); 
		}

		int cost = 0;
		for (int i = s0; i <= s; i++) {
			cost += distance(f1.tree(i), Tree.empty());
		}

		f1.addCachedValue(f1Int, emptyInt, cost);
		
		unregister(f1,s0,s,empty,0,0);
		return cost;		
	}

	// D(T_1[i],@)
	public int distance(Tree t1, Tree.Empty empty) {
		if (!register(t1,empty)) {
			return maxDistanceValue;
		}
		
		if (t1.hasCachedValueFor(empty)) {
			unregister(t1,empty);
			return t1.getCachedValue(empty);
		}

		int cost = distance(t1.forest(), Forest.empty()) + cf.cost(t1.label(), Label.empty()); 		
		t1.addCachedValue(empty, cost);
		
		unregister(t1,empty);
		return cost;
	}

	// D(@,F_2[j])
	public int distance(Forest.Empty empty, Forest f2) {
		if (!register(empty,f2)) {
			return maxDistanceValue;
		}
		
		int cost = distance(empty, f2, 1, f2.degree());
		
		unregister(empty,f2);
		return cost;
	}
	
	// Generalised version: D(@,F_2[j_t0,j_t])
	public int distance(Forest.Empty empty, Forest f2, int t0, int t) {
		if (!register(empty,0,0,f2,t0,t)) {
			return maxDistanceValue;
		}
	
		Forest.Interval emptyInt = empty.fullInterval();
		Forest.Interval f2Int = f2.interval(t0, t);
		if (empty.hasValueInCacheFor(emptyInt, f2Int)) {
			unregister(empty,0,0,f2,t0,t);
			return empty.getCachedValue(emptyInt, f2Int); 
		}

		int cost = 0;
		for (int j = t0; j <= t; j++) {
			cost += distance(Tree.empty(), f2.tree(j));
		}

		empty.addCachedValue(emptyInt, f2Int, cost);
		
		unregister(empty,0,0,f2,t0,t);
		return cost;
	}

	// D(@,T_2[j])
	public int distance(Tree.Empty empty, Tree t2) {
		if (!register(empty,t2)) {
			return maxDistanceValue;
		}
		
		if (empty.hasCachedValueFor(t2)) {
			unregister(empty,t2);
			return empty.getCachedValue(t2);
		}

		int cost = distance(Forest.empty(), t2.forest()) + cf.cost(Label.empty(), t2.label());
		empty.addCachedValue(t2, cost);
		
		unregister(empty,t2);
		return cost;
	}



	/* Required by Lemma 2 */

	// D(T_1[i],T_2[j])
	public int distance(Tree t1, Tree t2) {
		if (!register(t1,t2)) {
			return maxDistanceValue;
		}
		
		if (t1.hasCachedValueFor(t2)) {
			unregister(t1,t2);
			return t1.getCachedValue(t2);
		}

		int cost = 0;
	
		// The minimum of either (1), (2) or (3)

		// 1) D(@,T_2[j]) + min_(r:1->n_j){D(T_1[i],T_2[j_r]) - D(@,T_2[j_r])}
		int costAlt = distance(Tree.empty(), t2);
		Forest f2 = t2.forest();
		if (f2.degree() > 0) {
			int childCost = Integer.MAX_VALUE;
			for (int r = 1; r <= f2.degree(); r++) {
				Tree f2sub = f2.tree(r);
				int c = distance(t1, f2sub);
				c -= distance(Tree.empty(),f2sub);
				if (c < childCost) {
					childCost = c;
				}
			}
			costAlt += childCost;
		} else {
			// Comparing with the empty tree D(T_1[i],@), if T_2 has no children
			costAlt += distance(t1, Tree.empty());
		} 
		cost = costAlt;

		// 2) D(T_1[i],@) + min_(r:1->m_i){D(T_1[i_r],T_2[j]) - D(T_1[i_r],@)}
		costAlt = distance(t1, Tree.empty());
		Forest f1 = t1.forest();
		if (f1.degree() > 0) {
			int childCost = Integer.MAX_VALUE;
			for (int r = 1; r <= f1.degree(); r++) {
				Tree f1sub = f1.tree(r);
				int c = distance(f1sub, t2);
				c -= distance(f1sub, Tree.empty());
				if (c < childCost) {
					childCost = c;
				}
			}
			costAlt += childCost;
		} else {
			// Comparing with the empty tree D(@,T_2[j]), if T_1 has no children
			costAlt += distance(Tree.empty(), t2);
		}
		if (costAlt < cost) {
			cost = costAlt;
		}
		
		// 3) D(F_1[i],F_2[j]) + µ(l_1[i],l_2[j])
		costAlt = distance(f1, f2);
		costAlt += cf.cost(t1.label(), t2.label());
		if (costAlt < cost) {
			cost = costAlt;
		}

		t1.addCachedValue(t2, cost);
		
		unregister(t1,t2);
		return cost;
	}

	

	/* In part required by Lemma 2, but defined in Lemma 3 */

	// D(F_1[i],F_2[j])
	public int distance(Forest f1, Forest f2) { 
		return distance(f1, 1, f1.degree(), f2, 1, f2.degree());
	}

	// D(F_1[i_1,i_s], F_2[j_1,j_t])
	public int distance(Forest f1, int s0, int s, Forest f2, int t0, int t) {
		
		// For undefined intervals we replace a forest with the empty forest
		// Can both forests be equal to the empty forest?
		if (s0 > s && t0 > t) {
			return distance(Forest.empty(), Forest.empty());
		}
		if (s0 > s) {
			return distance(Forest.empty(), f2, t0, t);
		}
		if (t0 > t) {
			return distance(f1, s0, s, Forest.empty());
		}
		
		if (!register(f1,s0,s,f2,t0,t)) {
			return maxDistanceValue;
		}
		
		Forest.Interval f1Int = f1.interval(s0, s);
		Forest.Interval f2Int = f2.interval(t0, t);
		if (f1.hasValueInCacheFor(f1Int, f2Int)) {
			unregister(f1,s0,s,f2,t0,t);
			return f1.getCachedValue(f1Int, f2Int); 
		}

		int cost = 0;

		// The minimum of either (1), (2), (3), (4) or (5)
		
		// (1) D(F_1[i_1,i_s-1],F_2[j_1,j_t]) + D(T_1[i_s],@)
		int costAlt = distance(f1, s0, s-1, f2, t0, t) + distance(f1.tree(s), Tree.empty());
		cost = costAlt;
		
		// (2) D(F_1[i_1,i_s],F_2[j_1,j_t-1]) + D(@,T_2[j_t])
		costAlt = distance(f1, s0, s, f2, t0, t-1) + distance(Tree.empty(), f2.tree(t));
		if (costAlt < cost) {
			cost = costAlt;
		}

		// (3) D(F_1[i_1,i_s-1],F_2[j_1,j_t-1]) + D(T_1[i_s],T_2[j_t])
		costAlt = distance(f1, s0, s-1, f2, t0, t-1) + distance(f1.tree(s), f2.tree(t));
		if (costAlt < cost) {
			cost = costAlt;
		}

		// (4) µ(@,l_2[j_t]) + min_(k:1->s){D(F_1[i_1,i_k-1],F_2[j1,j_t-1]) + D(f_1[i_k,i_s],F_2[j_t])}
		costAlt = cf.cost(Label.empty(), f2.tree(t).label());
		// We have to do some additional checks to avoid the recursive loop
		if (costAlt < cost) {
			
			int childCost = maxDistanceValue;
			for (int k = s0; k < s; k++) {
				int c = distance(f1, s0, k-1, f2, t0, t-1);
				// If we've past the minimum jump over the next risky distance call
				if ((costAlt + c) >= cost) {
					continue;
				} else {
					c += distance(f1, k, s, f2, t, t);
					if (c < childCost) {
						childCost = c;
					}
					// I think this is the right thing to do here since we already tried to get
					// one value we don't have. Just increasing k won't bring us back to cached
					// values
					else if (c == maxDistanceValue) {
						childCost = c;
						break;
					}
				}
			}
			// This might be quite big if we didn't go into the loop which means this 
			// alternative will not be minimum. If we don't check we get a very small 
			// value because the childAlt value will be added to Integer.MAX_VALUE
			// which will give something close to Integer.MIN_VALUE
			if (childCost != maxDistanceValue) {
				costAlt += childCost;	
				if (costAlt < cost) {
					cost = costAlt;
				}
			}
		}

		// (5) µ(l_1[i_s],@) + min_(k:1-><t){D(F_1[i_1,i_s-1],F_2[j_1,j_k-1]) + D(F_1[i_s],F_2[j_k,j_t])}
		costAlt = cf.cost(f1.tree(s).label(), Label.empty());
		// Same as above -- we have to avoid the recursive loop
		if (costAlt < cost) {
			
			int childCost = maxDistanceValue;
			for (int k = t0; k < t; k++) {
				int c = distance(f1, s0, s-1, f2, t0, k-1);
				// We are once again jumping over the risky distance call 
				if ((costAlt + c) >= cost) {
					continue;
				} else {
					c += distance(f1, s, s, f2, k, t);
					if (c < childCost) {
						childCost = c;
					}
					// I think this is the right thing to do here since we already tried to get
					// one value we don't have. Just increasing k won't bring us back to cached
					// values
					else if (c == maxDistanceValue) {
						childCost = c;
						break;
					}
				}
			}
			if (childCost != maxDistanceValue) {
				costAlt += childCost;
				if (costAlt < cost) {
					cost = costAlt;
				}
			}
		}

		f1.addCachedValue(f1Int, f2Int, cost);
		
		unregister(f1,s0,s,f2,t0,t);
		return cost;
	}	
		
	// Call Stack
	
	public boolean register(Tree t1, Tree t2) {
		CallTrace call = new CallTrace();
		call.t1 = t1; call.t2 = t2;
		if (!callStack.isEmpty() && callStack.peek().equals(t1,t2)) {
			// Recursive call -- return false and don't add to stack
			/* DEBUG System.err.println("Recursive call t1="+ t1 + ",t2=" + t2); */
			return false;
		}
		callStack.addFirst(call);
		return true;
	}
	private CallTrace lastRecursiveCall = null;
	public boolean register(Forest f1, Forest f2) {
		CallTrace call = new CallTrace();
		call.f1 = f1; call.f2 = f2;
		if (!callStack.isEmpty() && callStack.peek().equals(f1, f2)) {
			// Recursive call -- return false and don't add to stack
			/* DEBUG System.out.println("*** Recursive call f1="+ f1 + ",f2=" + f2); */
			/* DEBUG
			if (lastRecursiveCall != null && lastRecursiveCall.equals(f1,f2)) {
				System.out.println("Two recursive calls in a row. Somethings probably wrong!");
			}
			*/
			lastRecursiveCall = call;
			return false;
		}
		callStack.addFirst(call);
		return true;		
	}
	public boolean register(Forest f1, int s0, int s, Forest f2, int t0, int t) {
		CallTrace call = new CallTrace();
		call.f1 = f1; call.s0 = s0; call.s = s;
		call.f2 = f2; call.t0 = t0; call.t = t;
		if (!callStack.isEmpty()) {
			// Check if there'a another call of the same type on the stack
			int distance = 0;
			for (Iterator<CallTrace> itr = callStack.iterator(); itr.hasNext();) {
				CallTrace callOnStack = itr.next();
				distance++;
				if (callOnStack.equals(f1,s0,s,f2,t0,t)) {
					// Recursive call -- return false and don't add to stack
					/* DEBUG System.out.println("*** Recursive call f1="+ f1 + ",s0=" + s0 + 
							",s=" + s + ",f2=" + f2 + ",t0=" + t0 + ",t=" + t + " -- distance=" + distance);
					if (distance > 1) {
						System.out.println("****** Recursive cycle with distance bigger than one");
					} */
					return false;
				}
			}
		}
		callStack.addFirst(call);
		return true;
	}
	
	public void unregister(Tree t1, Tree t2) {
		CallTrace call = callStack.removeFirst();
		if (!call.equals(t1, t2)) {
			throw new Error("There was a mismatch on the call stack, t1=" + 
					t1 + ",t2=" + t2);
		}
	}
	public void unregister(Forest f1, Forest f2) {
		CallTrace call = callStack.removeFirst();
		if (!call.equals(f1, f2)) {
			throw new Error("There was a mismatch on the call stack, f1=" + 
					f1 + ",f2=" + f2);
		}		
	}
	public void unregister(Forest f1, int s0, int s, Forest f2, int t0, int t) {
		CallTrace call = callStack.removeFirst();
		if (!call.equals(f1, s0, s, f2, t0, t)) {
			throw new Error("There was a mismatch on the call stack, f1=" + 
					f1 + ",s0=" + s0 + ",s=" + s + ",f2=" + f2 + ",t0=" + t0 + ",t=" + t);
		}
	}
	
	protected LinkedList<CallTrace> callStack = new LinkedList<CallTrace>();
	
	protected class CallTrace {
		Tree t1; Tree t2; Forest f1; Forest f2; int s0; int s; int t0; int t;
		public boolean equals(Tree t1, Tree t2) {
			return this.t1 == t1 && this.t2 == t2;
		}
		public boolean equals(Forest f1, Forest f2) {
			return this.f1 == f1 && this.f2 == f2;
		}
		public boolean equals(Forest f1, int s0, int s, Forest f2, int t0, int t) {
			return this.f1 == f1 && this.s0 == s0 && this.s == s 
				&& this.f2 == f2 && this.t0 == t0 && this.t == t;
		}
	}
}
